实现单链表

2023-12-27 11:57| 来源: 网络整理| 查看: 265

单链表的结构

单链表结点的组成：

元素链接域（保存下一结点的地址）在这里插入图片描述

在单链表里，表里的n 个结点通过链接形成一条结点链。从表里的任一个结点都可以找到保存下一个元素的结点。链表中的一个重要部分就是头指针。头指针保存着链表首结点的标识，通过头指针可以十分方便的对链表进行：访问元素、遍历、增删改查等操作

TODO:补充单链表的特性

实现定义节点类

节点是链表的基本组成部分

class Node : # 只定义初始化操作 def __init__(self, elm, next_=None): self.elem = elem # 因为Python中next是一个内置的函数，为区分，故在变量名后添加"_" self.next_ = next_ 定义单链表类 # 单链表类只有一个 _head 域，表示单链表的头指针 class SingleList: def __init__(self): self._head = None

变量前的单下划线表示私有变量，不要在对象的外部去访问。python语言没有为定义私有变量提供专门的机制，只能通过约定和良好的编程习惯来保护对象的私有属性。

定义异常类

为了能合理处理一些链表操作中遇到的错误状态，如在执行方法时遇到了无法操作的错误参数，首先定义一个异常类LinkedListUnderflow，这里将它定义为标准异常类ValueError的子类，pass表示空语句，即什么都不做。

TODO: 在这里直接抛出ValueError也没问题，但定义了自己的异常类就可以写专门的异常处理器。

class LinkedListUnderflow(ValueError): pass 对链表的具体操作删除链表

在Python中，如果一个对象未被引用，则该对象会被当做垃圾并进行回收。所以删除链表只需将头指针设为None，使得链表对象不被引用

def del_list(self): self._head = None 判断表空

在Python里检查_head值是否为None，如果为None，则说明_head不指向任何对象

def is_empty(self): return self._head is None 判断表满

因为链表没有一个固定的容量，可以动态扩充，所以在内容充足的情况下，链表是不会满的

链表长度

算法描述：

创建计数器遍历至最后一个节点

代码实现：

def length(self): '''计算链表长度''' point = self._head count = 1 while point.next_ != None: point = point.next_ count += 1 return count

思考1：为什么需要新建一个point变量

遍历链表

算法描述：

创建计数器遍历至最后一个节点

算法实现：

def traverse(self): '''遍历链表''' point = self._head index = 0 while point.next_ != None: index += 1 print("第", index, "个元素是：", point.elem) point = point.next_ print("第", (index + 1), "个元素是：", point.elem)

思考2：如何确定循环结束的条件？

定位元素–按下标定位

算法描述：

判断下标的合法性根据计数器找指定下标的元素

代码实现：

def index(self, index_): '''定位元素--按下标定位''' if index_ >= self.length() and index_ = self.length() and index

【本文地址】

公司简介

联系我们